<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta name="description" content="容斥原理 用于解决一类，在已知任意 $m$ 个集合交集大小的情况下，多个集合求并集大小的问题。 事实上，容斥原理 也能解决很多计数、数论甚至概率等方面的问题。">
<meta property="og:type" content="article">
<meta property="og:title" content="「学习总结」容斥原理">
<meta property="og:url" content="2021/%E3%80%8C%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93%E3%80%8D%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:description" content="容斥原理 用于解决一类，在已知任意 $m$ 个集合交集大小的情况下，多个集合求并集大小的问题。 事实上，容斥原理 也能解决很多计数、数论甚至概率等方面的问题。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-01-04T13:56:17.000Z">
<meta property="article:modified_time" content="2021-01-09T13:14:21.233Z">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="学习总结">
<meta property="article:tag" content="数学">
<meta property="article:tag" content="容斥原理">
<meta property="article:tag" content="计数">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="2021/「学习总结」容斥原理/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>「学习总结」容斥原理 | Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86"><span class="nav-number">1.</span> <span class="nav-text">容斥原理</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AE%9A%E4%B9%89%E5%8F%8A%E8%AF%81%E6%98%8E"><span class="nav-number">1.1.</span> <span class="nav-text">定义及证明</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AE%A1%E6%95%B0%E9%97%AE%E9%A2%98%E7%9A%84%E8%BD%AC%E5%8C%96"><span class="nav-number">1.2.</span> <span class="nav-text">计数问题的转化</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86%E6%A0%97%E9%A2%98%EF%BC%88%E4%BB%AC%EF%BC%89"><span class="nav-number">1.3.</span> <span class="nav-text">容斥原理栗题（们）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E4%B8%80"><span class="nav-number">1.3.1.</span> <span class="nav-text">栗题一</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E4%BA%8C"><span class="nav-number">1.3.2.</span> <span class="nav-text">栗题二</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E4%B8%89"><span class="nav-number">1.3.3.</span> <span class="nav-text">栗题三</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E5%9B%9B"><span class="nav-number">1.3.4.</span> <span class="nav-text">栗题四</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E4%BA%94"><span class="nav-number">1.3.5.</span> <span class="nav-text">栗题五</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E5%85%AD"><span class="nav-number">1.3.6.</span> <span class="nav-text">栗题六</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%97%E9%A2%98%E4%B8%83"><span class="nav-number">1.3.7.</span> <span class="nav-text">栗题七</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%9C%B4%E7%B4%A0%E5%81%9A%E6%B3%95"><span class="nav-number">1.3.7.1.</span> <span class="nav-text">朴素做法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%BC%98%E5%8C%96%E5%81%9A%E6%B3%95"><span class="nav-number">1.3.7.2.</span> <span class="nav-text">优化做法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%89%A9%E5%B1%95%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86"><span class="nav-number">1.4.</span> <span class="nav-text">扩展容斥原理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Min-max-%E5%AE%B9%E6%96%A5"><span class="nav-number">1.5.</span> <span class="nav-text">Min-max 容斥</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E3%80%8CPKUWC2018%E3%80%8D%E9%9A%8F%E6%9C%BA%E6%B8%B8%E8%B5%B0"><span class="nav-number">1.5.1.</span> <span class="nav-text">「PKUWC2018」随机游走</span></a></li></ol></li></ol></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2021/「学习总结」容斥原理/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          「学习总结」容斥原理
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-01-04 21:56:17" itemprop="dateCreated datePublished" datetime="2021-01-04T21:56:17+08:00">2021-01-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-01-09 21:14:21" itemprop="dateModified" datetime="2021-01-09T21:14:21+08:00">2021-01-09</time>
      </span>

  
    <span id="2021/「学习总结」容斥原理/" class="post-meta-item leancloud_visitors" data-flag-title="「学习总结」容斥原理" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2021/「学习总结」容斥原理/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2021/「学习总结」容斥原理/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>7.5k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>7 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <p><strong>容斥原理</strong> 用于解决一类，在已知任意 $m$ 个集合交集大小的情况下，多个集合求并集大小的问题。</p>
<p>事实上，<strong>容斥原理</strong> 也能解决很多计数、数论甚至概率等方面的问题。</p>
<a id="more"></a>

<h1 id="容斥原理"><a href="#容斥原理" class="headerlink" title="容斥原理"></a>容斥原理</h1><h2 id="定义及证明"><a href="#定义及证明" class="headerlink" title="定义及证明"></a>定义及证明</h2><p>设 $U$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$ ，拥有属性 $P_i$ 的元素构成集合 $S_i$ ，那么</p>
<p>$$<br>\begin{equation}<br>\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i&lt;a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|<br>\end{equation}<br>$$<br>其中 $a$ 为任意长度为 $m$ 且 值域为 $[1, n]$ 的不重无序数列。</p>
<p>通过定义可知，<strong>容斥原理</strong> 用于解决一类，在已知任意 $m$ 个集合交集大小的情况下，多个集合求并集大小的问题。</p>
<p>对于有限制条件的计数问题，可以转化成求<strong>集合交并大小</strong>问题，进而通过<strong>容斥原理</strong>解决。</p>
<p>关于容斥原理的证明，其实就是要保证并集中的每一个元素对答案的贡献为 $1$ 。</p>
<p>对于元素 $x$，假设它出现在 $T_1,T_2,\cdots,T_m$ 的集合中，那么它的出现次数为</p>
<p>$$<br>\begin{split}<br>Cnt=&amp;|\{T_i\}|-|\{T_i\cap T_j|i&lt;j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i&lt;a_{i+1} \right \} \right|\\<br>&amp;+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\<br>=&amp;C_m^1-C_m^2+\cdots+(-1)^{m-1}C_m^m\\<br>=&amp;C_m^0-\sum_{i=0}^m(-1)^iC_m^i\\<br>=&amp;1-(1-1)^m=1<br>\end{split}<br>$$</p>
<h2 id="计数问题的转化"><a href="#计数问题的转化" class="headerlink" title="计数问题的转化"></a>计数问题的转化</h2><p>可以考虑把具有相同属性的计数对象放入同一集合。然后根据题目要求，求出同时具有某些属性的技术对象个数（即：属性对应的集合交集）。<br>$$<br>\begin{equation}<br>\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|<br>\end{equation}<br>$$<br>由于容斥原理本身是求集合并集大小，但是可以通过 上式 转化为求集合交集大小问题。</p>
<h2 id="容斥原理栗题（们）"><a href="#容斥原理栗题（们）" class="headerlink" title="容斥原理栗题（们）"></a>容斥原理栗题（们）</h2><h3 id="栗题一"><a href="#栗题一" class="headerlink" title="栗题一"></a>栗题一</h3><p>详见<a target="_blank" rel="noopener" href="https://oi-wiki.org/math/inclusion-exclusion-principle/#_5">不定方程非负整数解计数</a>。</p>
<div class="note info"><p>对于限制元素数量下界的要求，处理方式都可以采用，直接对总数减去这个元素的下界，计算取值时直接不考虑下界即可。</p>
</div>

<h3 id="栗题二"><a href="#栗题二" class="headerlink" title="栗题二"></a>栗题二</h3><div class="note info"><p>对于一个 $1$~$n$ 的排列 $P$，若 $\forall i ,P_i \not = i$ 则称其为错位排列。给出 $n$ ，求长度为 $n$ 的错位排列个数。</p>
</div>

<p>考虑全集 $|\mathbb{U}|=n!$ ，元素属性就是 $P_i \not = i$，答案就是 $\left|\bigcap_{i=1}^{n}\limits{S_i}\right|$。</p>
<p>考虑到：<br>$$<br>\begin{equation}<br>\left|\bigcap_{i=1}^{n}S_i\right|=|\mathbb{U}|-\left|\bigcup_{i=1}^n\overline{S_i}\right|<br>\end{equation}<br>$$<br>易知：$\overline{S_i}$ 就是所有 $P_i = i$ 的排列。</p>
<p>考虑到：<br>$$<br>\begin{split}<br>\left|\bigcup_{i=1}^n\overline{S_i}\right|&amp;=\sum_{k=1}^{n}\limits{(-1)^{k-1}\sum_{a_1,\dots ,a_k}\limits{ \left|\bigcap_{i=1}^{k}\limits{S_{a_i}}\right|  }}\<br>&amp;=\sum_{k=1}^{n}\limits{(-1)^{k-1}\dbinom{n}{k}(n-k)!}\<br>\end{split}<br>$$<br>综合上式，得出长度为 $n$ 的错位排列数为：</p>
<p>$$<br>D_n=n!-\sum_{k=1}^{n}\limits{(-1)^{k-1}\dbinom{n}{k}(n-k)!}<br>$$</p>
<h3 id="栗题三"><a href="#栗题三" class="headerlink" title="栗题三"></a>栗题三</h3><div class="note info"><p>A 和 B 喜欢对图（不一定连通）进行染色，而他们的规则是，相邻的结点必须染同一种颜色。</p>
<p>今天 A 和 B 玩游戏，对于 $n$ 阶 <strong>完全图</strong>  $G=(V,E)$ 。他们定义一个估价函数 $F(S)$ ，其中 S 是边集， $S\subseteq E$ .</p>
<p>$F(S)$ 的值是对图 $G’=(V,S)$ 用 $m$ 种颜色染色的总方案数。</p>
<p>他们的另一个规则是，如果 $|S|$ 是奇数，那么 A 的得分增加 $F(S)$ ，否则 B 的得分增加 $F(S)$ . 问 A 和 B 的得分差值。</p>
</div>

<p><del>出题人千辛万苦凑出的式子</del></p>
<p>考虑形式化的定义答案：<br>$$<br>Ans=\sum_{S\subseteq E}(-1)^{|S|-1}F(S)<br>$$<br>设集合 $Q_{(i, j)}$ 中的元素为所有 $(i, j)$ 有边相连的图的染色方案。考虑到相邻的节点（有边相连）必须染成相同的颜色，所以两节点 $i, j$ 有边相连即 节点 $i, j$ 染成相同的颜色。</p>
<p>易知：<br>$$<br>F(S)=\left|\bigcap_{e\in S}\limits{Q_e}\right|<br>$$<br>带入原式即：（这里用到了容斥原理的逆用）<br>$$<br>\begin{split}<br>Ans&amp;=\sum_{S\subseteq E}(-1)^{|S|-1}\left|\bigcap_{e\in S}\limits{Q_e}\right|\<br>&amp;=\left|\bigcup_{e\in E}\limits{Q_e}\right|<br>\end{split}<br>$$<br>答案变成：对一张完全图染色，存在任意两个点同色的方案数。</p>
<p>考虑到两两点都异色的染色方案数为 $A_m^n$。</p>
<p>所以答案为：<br>$$<br>m^n-A_m^n<br>$$<br>其实容斥原理本质上是集合间交集和并集大小之间的转化。</p>
<h3 id="栗题四"><a href="#栗题四" class="headerlink" title="栗题四"></a>栗题四</h3><div class="note info"><p>求出：<br>$$<br>\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)<br>$$<br>其中：$n \le 10^5$</p>
</div>
<p>考虑枚举 <code>gcd</code> ，设函数 $f(g)$ 为 <strong>以 g 为最大公约数的数对个数</strong>。<br>易知：<br>$$<br>f(g) = \lfloor\frac{n}{g}\rfloor^2 - \sum_{i=2}^{i \times g \le n}f(i \times g)<br>$$<br>考虑到当 $g &gt; \frac{n}{2}$ 时，可以直接得到答案。其余的值逆向递推即可。</p>
<h3 id="栗题五"><a href="#栗题五" class="headerlink" title="栗题五"></a>栗题五</h3><p><a target="_blank" rel="noopener" href="https://oi-wiki.org/math/inclusion-exclusion-principle/#_14">容斥原理推导欧拉函数通项公式</a></p>
<h3 id="栗题六"><a href="#栗题六" class="headerlink" title="栗题六"></a>栗题六</h3><div class="note info"><p>询问 $1-n$ 中有多少数字可以表示成 $x^y, y &gt; 1$ 的形式。其中 $n \le 10^{18}$</p>
</div>
<p>枚举 $x$ 的复杂度为 $\mathcal{O}(\sqrt n)$ 的。考虑枚举 $y$ ，这样的复杂度仅为 $\mathcal{O}(\log n)$。枚举一个 $y$ 后，合法的数字有 $\sqrt[y]{n}$ 个。</p>
<p>易知，当  $y$ 不等于质数积时，贡献为 0。例如 $y=4$ 时，这里的答案一定被 $y=2$ 时算过一次了。</p>
<p>其余的情况，根据容斥原理的套路，可以发现，容斥系数为 $-\mu(y)$ 。 <strong>莫比乌斯函数</strong>也被称之为<strong>数论容斥系数</strong>。</p>
<h3 id="栗题七"><a href="#栗题七" class="headerlink" title="栗题七"></a>栗题七</h3><div class="note info"><p>DAG 计数。给出点数 $n$ ，输出 $n$ 个点的带标号 DAG 的数量，对大质数取模。<br>其中 $n\le 5 \times 10^3$</p>
</div>

<p>考虑到对于一个 DAG 来说，将其入度为 0 的点剖去之后，剩下的图也是一个 DAG 。这样就成功划分了子问题。</p>
<h4 id="朴素做法"><a href="#朴素做法" class="headerlink" title="朴素做法"></a>朴素做法</h4><p>设 $f(i, j)$ 表示 $i$ 个点的 DAG，有 $j$ 个点的入度为 $0$，考虑转移：枚举剥去这 $j$ 个点后会剩下多少个入度为 0 的点。<br>$$<br>f(i, j) = \dbinom{i}{j} \sum_{k=1}^{i-j}\limits{(2^j-1)^k 2^{j(i-j-k)}f(i-j, k)}<br>$$<br>后面的式子分别为：</p>
<ul>
<li>$\dbinom{i}{j}$ ：在 $i$ 个标号中选出 $j$ 个充当入度为 $0$ 的点。</li>
<li>$(2^j-1)^k$：对于这 $k$ 个入度为 0 的点，他们可以和之前的 $j$ 个点随意连边（除了不连任何边的情况）。</li>
<li>$2^{j(i-j-k)}$：对于这 $j$ 个点，还可以与除这 $k$ 个点剩下的 $i-j-k$ 个点任意连边，一共有 $i \times (i-j-k)$ 条边可以连。<br>这样的做法是 $\mathcal{O}(n^3)$ 的</li>
</ul>
<h4 id="优化做法"><a href="#优化做法" class="headerlink" title="优化做法"></a>优化做法</h4><div class="note info"><p>容斥原理的一般化：<br>对于两个集合函数 $f(S), g(S)$：<br>$$<br>\begin{equation} \label{rev0}<br>f(S) = \sum_{T \subseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \subseteq S}\limits{(-1)^{|S| - |T|}f(T)}<br>\end{equation}<br>$$</p>
<p>$$<br>\begin{equation} \label{rev1}<br>f(S) = \sum_{T \supseteq S}\limits{g(T)}\ \ \Longleftrightarrow\ \ g(S) = \sum_{T \supseteq S}\limits{(-1)^{|S| - |T|}f(T)}<br>\end{equation}<br>$$</p>
</div>

<p>设：$f(n, S)$ 为 $n$ 个点的 DAG 中 $S$ 中的点度数为 $0$，类似地，$g(n, S)$ 为 $n$ 个点的 DAG  中 至少 $S$ 中的点度数为 $0$（钦点）。<br>易知：<br>$$<br>\begin{equation} \label{solg}<br>g(n, S) = 2^{|S|(n - |S|)}g(n, \varnothing)<br>\end{equation}<br>$$</p>
<p>其中 $g, f$ 有如下关系。<br>$$<br>\begin{equation} \label{gfcon}<br>g(n, S)=\sum_{T \supseteq S}f(n, T)<br>\end{equation}<br>$$<br>根据 $(\ref{rev1})$：<br>$$<br>\begin{equation} \label{label_QAQ}<br>f(n, S) = \sum_{T \supseteq S}(-1)^{|S| - |T|}g(n, T)<br>\end{equation}<br>$$</p>
<p>目的是求出 $g(n, \varnothing)$：<br>$$<br>\begin{split}<br>g(n, \varnothing) &amp;=\sum_{T \not = \varnothing}f(n, T)\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T)<br>\end{split}<br>$$<br>分别带入 $(\ref{label_QAQ})$ ，$(\ref{solg})$<br>$$<br>\begin{split}<br>g(n, \varnothing) &amp;=\sum_{T \not = \varnothing}f(n, T)\\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}f(n, T)\\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - |T|}g(n, S)   \\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - |T|}2^{|S|(n-|S|)}g(n-|S|, \varnothing)   \\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{S \supseteq T}(-1)^{|S| - i}2^{|S|(n-|S|)}g(n-|S|, \varnothing)   \\<br>&amp;=\sum_{i=1}^{n}\sum_{T, |T|=i}  \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing)   \\<br>&amp;=\sum_{i=1}^{n} \dbinom{n}{i}  \sum_{k=i}^{n}\dbinom{n-i}{k-i}(-1)^{k - i}2^{k(n-k)}g(n-k, \varnothing)   \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{i}\dbinom{n-i}{k-i}(-1)^{k-i} \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\sum_{i=1}^{k}\dbinom{n}{k}\dbinom{k}{i}(-1)^{k-i} \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\sum_{i=1}^{k}\dbinom{k}{i}(-1)^{k-i} \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left (\sum_{i=0}^{k}\dbinom{k}{i}(-1)^{k-i}1^i \right)- (-1)^k\right] \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}g(n-k, \varnothing)\dbinom{n}{k}\left[\left ( 1-1 \right)^k- (-1)^k\right] \\<br>&amp;=\sum_{k=1}^{n}2^{k(n-k)}\dbinom{n}{k}(-1)^{k-1} g(n-k, \varnothing)\<br>\end{split}<br>$$</p>
<p>这样的做法是 $\mathcal{O}(n^2)$ 的。</p>
<h2 id="扩展容斥原理"><a href="#扩展容斥原理" class="headerlink" title="扩展容斥原理"></a>扩展容斥原理</h2><blockquote>
<p>gugugu</p>
</blockquote>
<h2 id="Min-max-容斥"><a href="#Min-max-容斥" class="headerlink" title="Min-max 容斥"></a>Min-max 容斥</h2><p>$$<br>\begin{equation}\label{max_min}<br>\operatorname{max} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{min} T<br>\end{equation}<br>$$</p>
<p>$$<br>\begin{equation}<br>\operatorname{min} S = \sum_{T \subseteq S} (-1)^{|T| - 1} \operatorname{max} T<br>\end{equation}<br>$$</p>
<h3 id="「PKUWC2018」随机游走"><a href="#「PKUWC2018」随机游走" class="headerlink" title="「PKUWC2018」随机游走"></a>「PKUWC2018」随机游走</h3><div class="note info"><p>给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。</p>
<p>有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。</p>
<p>特别地，点 $x$（即起点）视为一开始就被经过了一次。</p>
<p>答案对 $998244353 $ 取模。</p>
<p>对于 $100%$ 的数据，有 $1\leq n\leq 18$，$1\leq Q\leq 5000$，$1\leq k\leq n$</p>
</div>

<p>设 $A_i$ 表示到达从 $x$ 点出发第一次到达点 $i$ 的期望时间。</p>
<p>易知：答案就是 $E\left(\max_{i\in S}\limits{(x_i)}\right)$。需要注意的是： $E\left(\max_{i\in S}\limits{(x_i)}\right) \not = \max_{i \in S}\limits{\left(E(x_i)\right)}$，<br>详见<a target="_blank" rel="noopener" href="https://www.luogu.com.cn/blog/command-block/min-max-rong-chi-xiao-ji">博文</a></p>
<blockquote>
<p>这是非常有用的，因为期望下的  $\max$ 和  $\min$ 是很难求的。</p>
<p>假设有  $a,b$ 两个不相关变量，则  $E(\max(a,b))≠\max(E(a),E(b))$。</p>
<p>例子：抛硬币，$a=b= \begin{cases} 0\ (50\%) \\ 1\ (50\%) \end{cases}$ ,则  $E(a)=E(b)=\dfrac{1}{2}$</p>
<p>那么  $\max(a,b)=\begin{cases}\max(0,0)\ (25\%)\\ \max(0,1)\ (25\%)\\ \max(1,0)\ (25\%)\\ \max(1,1)\ (25\%) \end{cases}$ ,则  $E(\max(a,b))=0.75$</p>
<p>但是 $\max(E(a),E(b))=0.5$所以期望不能大力拆  $\max$ 或  $\min$ 。</p>
<p>——引用自 command_block 的博客。</p>
</blockquote>
<p>由 $(\ref{max_min})$ 可知：<br>$$<br>\begin{equation}<br>E\left(\max_{i \in S}\limits{x_i}\right)=\sum_{T \subseteq S}(-1)^{|T|-1}E\left(\min_{i \in T}x_i\right)<br>\end{equation}<br>$$</p>
<p>考虑如何求出 $E\left(\min_{i \in T}\limits{x_i}\right)$</p>
<p>相当于从点 $x$ 出发，首次到达 $T$ 中的任意一点的期望时间。</p>
<p>设 $f(i)$ 表示从结点 $i$ 出发，到达 $T$ 首次中的点的期望时间。</p>
<p>对于 $i \in T, f(i)=0$ </p>
<p>对于 $i \notin T, f(i) = \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right)$</p>
<p><del>据说是</del>经典套路：</p>
<p>待定系数法，设 $f(i)=A_i \times f(fa_i) + B_i$<br>$$<br>\begin{split}<br>f(i) &amp;= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(f(v) + 1\right)} + f(fa_i) + 1\right) \\<br>&amp;= \dfrac{1}{deg_i}\left(\sum_{v}\limits{\left(A_vf(i)+B_v + 1\right)} + f(fa_i) + 1\right) \\<br>&amp;= \dfrac{1}{deg_i -\sum{A_v}} f(fa_i)+\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}}<br>\end{split}<br>$$<br>所以：$A_i =  \dfrac{1}{deg_i -\sum{A_v}}, B_i=\dfrac{deg_i+\sum{B_v}}{deg_i-\sum{A_v}}$</p>
<p>特殊的：对于 $i \in T$ , $A_i = B_i = 0$。</p>
<p>这里的 $A, B$ 可以直接通过树上 dp 求出。同时，可以递推出 $f(i)$ 的值。</p>
<p>设 $F(T) = (-1)^{|T|-1}f(x)$ ,答案就是 $ \sum_{T \subseteq S}\limits{F(T)}$</p>
<p>考虑到这东西是子集和变换，使用 FMT (快速莫比乌斯变换)  预处理即可。然后 $O(1)$ 回答。</p>
<div class="note danger"><p>参考文献：</p>
<ul>
<li>国家集训队 2013 论文集《浅谈容斥原理》成都七中 王迪 </li>
</ul>
</div>
    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a target="_blank" href="//tags/学习总结/" rel="tag noopener"># 学习总结</a>
              <a target="_blank" href="//tags/数学/" rel="tag noopener"># 数学</a>
              <a target="_blank" href="//tags/容斥原理/" rel="tag noopener"># 容斥原理</a>
              <a target="_blank" href="//tags/计数/" rel="tag noopener"># 计数</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2020/「学习总结」计数问题/" rel="prev" title="「学习总结」计数问题">
                  <i class="fa fa-chevron-left"></i> 「学习总结」计数问题
                </a>
            </div>
            <div class="post-nav-item">
            </div>
          </div>
    </footer>
  </article>
  
  
  



      
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "2021/「学习总结」容斥原理/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
